package com.asa.jihe.D;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.asa.jihe.TuXinXiangJiao;
import com.asa.jihe.B.Convex_Hull;
import com.asa.jihe.utils.Copy;
import com.asa.jihe.utils.Graph;
import com.asa.jihe.utils.Line;
import com.asa.jihe.utils.Point;
import com.asa.jihe.utils.ToLeftTest;

/**
 * 将一个图，按照它的顶点，划分为一个一个的三角形
 * @author asa
 *
 */
public class GraphSplitTriangle {
	
	
	
	//切耳法
	//这里对于耳朵的定义就是一个点可以和其他的点构成三角，而这个三角形不在图内
	//那么这个点与它相邻的两个点所组成的点就是耳朵了
	//
	public static void main(String[] args) {
		
//		func1();
		
		//我觉得太麻烦了，打算随意按照自己的思考方式来做
		Graph graph = inittu();
		func2(graph);
		
		
		//对于图形里面存着图形（图形是空心的）这种情况，我们可以先将内包的图的点，和最外层图的点相连
		//通过这样的方式，我们可以将原来的图形再分解成很多个小的凸包的子图形，这个分离过程其实还算很麻烦的
		//而且这些内部的图也需要先转化为凸包的，这个要比方法二的那种简单，这个只需要找一次即可
		//因为太麻烦了，我就先不实现了，仅仅把思路写在这里
		
		/******************************************************/
//		func3(graph);

		
	}

	/**
	 * 这里直接用扫描法来处理，我是比较不喜欢平面扫描的，那种方法是对有限屏幕进行扫描，而交叉点不是整数它也不好处理
	 * 但我喜欢这种，依次点扫描
	 * 这里将一个图分成两条线，
	 * 留白吧
	 * @param graph
	 */
	private static void func3(Graph graph) {
		
		List<Line> lines = graph.lines;

		TuXinXiangJiao.nishizhen(lines);
		List<Point> graphtopoints = Copy.graphtopoints(graph);
		
		Point maxypoint = null;
		Point minypoint = null;
		
		int maxindex = 0;
		int minindex = 0;

		for (int i = 0; i < graphtopoints.size(); i++) {
			Point point = graphtopoints.get(i);
			System.out.println(point);
			if (maxypoint==null) {
				maxypoint = point;
			}else {
				if (maxypoint.y<point.y) {
					maxypoint = point;
					maxindex = i;
				}
			}
			
			if (minypoint==null) {
				minypoint = point;
			}else {
				if (minypoint.y>point.y) {
					minypoint = point;
					minindex = i;
				}
			}
			
		}
		System.out.println("=========================");
		System.out.println(maxypoint);
		System.out.println(minypoint);

		
		List<Point> lian1 = new LinkedList<>();
		List<Point> lian2 = new LinkedList<>();
		if (minindex<maxindex) {
			for (int i = minindex; i < maxindex; i++) {
				lian1.add(graphtopoints.get(i));
			}
			for (int i = maxindex; i < graphtopoints.size(); i++) {
				lian2.add(graphtopoints.get(i));

			}
			
			for (int i = 0; i < minindex; i++) {
				lian2.add(graphtopoints.get(i));
			}
			
			
		}else {
			
			for (int i = maxindex; i < minindex; i++) {
				lian2.add(graphtopoints.get(i));
			}
			for (int i = minindex; i < graphtopoints.size(); i++) {
				lian1.add(graphtopoints.get(i));

			}
			
			for (int i = 0; i < maxindex; i++) {
				lian1.add(graphtopoints.get(i));
			}
		}
		System.out.println("================================");

		for (int i = 0; i < lian1.size(); i++) {
			System.out.println(lian1.get(i));
		}
		System.out.println("================================");
		for (int i = 0; i < lian2.size(); i++) {
			System.out.println(lian2.get(i));
		}
		
		
		
		List<Point> stack = new LinkedList<>();
		

		
		
		
		
	}

	
	
	
	
	


	/**
	 * 我做成了，但有局限性，这个不能是空心的，而且对于凸包的计算，也有很高的复杂度
	 * 不止是不可以空心，没有把新生成的三角抛分是否包含原来的点的情况考虑进去
	 * 要打补丁，打好了，没用，这个算法是有问题的，不要用
	 * @param graph
	 */
	public static List<Line> func2(Graph graph) {
		List<Line> lines = graph.lines;

		TuXinXiangJiao.nishizhen(lines);
		List<Point> graphtopoints = Copy.graphtopoints(graph);
		System.out.println("从图中将点获取数"+graphtopoints.size());
		List<Point> containspoints = new ArrayList<>();

		List<Line> lineangle = new ArrayList<>();//这个就记录了组成三角形的点内接线

		
		
		
		while (true) {
			
			
			/**
			 * 形成凸包
			 */
			List<Line> method0 = Convex_Hull.method0(graphtopoints);
			
			System.out.println("形成凸包边数："+method0.size());
			
			for (int i = 0; i < method0.size(); i++) {
				System.out.println(method0.get(i));
			}
			
			List<Point> method2 = Copy.line2point(method0);
			
//			List<Point> method2 = Convex_Hull.method1(graphtopoints);
			System.out.println("当前闭包点数："+method2.size());
			
			for (int i = 0; i < graphtopoints.size(); i++) {
				boolean contains = method2.contains(graphtopoints.get(i));
				if (!contains) {
					containspoints.add(graphtopoints.get(i));
				}
			}
			
			System.out.println("内包含的点："+containspoints.size());
			if (containspoints.size()==0) {
				break;
			}
			
			System.out.println("开始前去除点");
			
			//我们现在拿到了凸包点和包含点了
			
			//去找凸包点和包含点直接的拐点,我们剔除拐点，但可惜的是每次只能剔除1个，我隐约觉得可以剔除两个，但会有些麻烦
			boolean zhaoguaidian = false;
			Point point = null;

			a:for (int i = 0; i < graphtopoints.size(); i++) {
				
				point = graphtopoints.get(i);
				System.out.println(zhaoguaidian);
				if (zhaoguaidian) {
					System.out.println("去找拐点了...........："+point+"   "+!method2.contains(point));
					
					
					
					
					
					if (!method2.contains(point)) {//这个就是拐点了
						System.out.println("找到拐点了...........："+point);
						if (i==0) {
							Line line = new Line();
							
							line.spoint = graphtopoints.get(graphtopoints.size()-1);
							line.epoint = graphtopoints.get(i+1);
							lineangle.add(line);
							
						}else if (i==(graphtopoints.size()-1)) {
							Line line = new Line();
							
							line.spoint = graphtopoints.get(i-1);
							line.epoint = graphtopoints.get(0);
							lineangle.add(line);
						}else {
							Line line = new Line();
							
							line.spoint = graphtopoints.get(i-1);
							line.epoint = graphtopoints.get(i+1);
							lineangle.add(line);
						}
						break;
						
					}
					
					
				}else if (containspoints.contains(point)) {
					zhaoguaidian = true;
					if (i>0) {
						System.out.println("找到拐点了...........："+point);
						if (i>1) {
							Line line = new Line();
							line.spoint = graphtopoints.get(i-2);
							line.epoint = graphtopoints.get(i);
							point = graphtopoints.get(i-1);
							
							for (int j = 0; j < graphtopoints.size(); j++) {//补丁。。防止生成的三角形包含点
								boolean inTriangleTest = ToLeftTest.inTriangleTest(graphtopoints.get(j), line.spoint, point, line.epoint);
								if (inTriangleTest) {
									continue a;
								}
							}
							
							lineangle.add(line);
						}else if(i==1) {
							Line line = new Line();
							line.spoint = graphtopoints.get(graphtopoints.size()-1);
							line.epoint = graphtopoints.get(i);
							point = graphtopoints.get(i-1);
							
							for (int j = 0; j < graphtopoints.size(); j++) {//补丁。。防止生成的三角形包含点
								boolean inTriangleTest = ToLeftTest.inTriangleTest(graphtopoints.get(j), line.spoint, point, line.epoint);
								if (inTriangleTest) {
									continue a;
								}
							}
							lineangle.add(line);

						}
						
						break;
					}
					
				}	
			}
			
			
			System.out.println("移除拐点："+point);
			graphtopoints.remove(point);
			containspoints = new ArrayList<>();
			System.out.println("还剩的点数："+graphtopoints.size());
			
		}
		
		System.out.println("循环已经跑完了");
		
		
		
		
		//现在，这个图像就是一个凸包的图形了
		for (int i = 0; i < graphtopoints.size(); i++) {
			System.out.println(graphtopoints.get(i));
		}
		
		
		for (int i = 0; i < lineangle.size(); i++) {
			System.out.println(lineangle.get(i));
		}
		
		System.out.println("=========================================");
		for (int i = 2; i < graphtopoints.size()-1; i++) {
			Line line = new Line();
			line.spoint = graphtopoints.get(0);
			line.epoint = graphtopoints.get(i);
			lineangle.add(line);
		}
		
		
		for (int i = 0; i < lineangle.size(); i++) {
			System.out.println(lineangle.get(i));
		}
		
		return lineangle;
	}




	/**
	 * 方法1
	 * 对于凸包的可行，
	 * 对于狭长的弯曲的图不行，等等，好像没问题			确实有问题
	 */
	public static List<Line> func1(Graph graph) {
//		Graph graph = inittu();
		
		List<Line> lines = graph.lines;
		
		//这里先不考虑内部是存在空心的情况，只考虑一般的外包类型的
		List<Line> lineangle = new ArrayList<>();//这个就记录了组成三角形的点内接线

		TuXinXiangJiao.nishizhen(lines);
		List<Point> graphtopoints2 = Copy.graphtopoints(graph);
		List<Point> graphtopoints = Copy.graphtopoints(graph);
		
		for (int i = 0; i < graphtopoints.size(); i++) {
			System.out.println(graphtopoints.get(i));
		}
		int asa = 0;
		
		while (graphtopoints.size()>2) {//这种方式有点呆，是否考虑用栈的方式来实现
			System.out.println("要确认的点："+graphtopoints.size());

			System.out.println("已经找到了的线："+lineangle.size());

			if (asa>100) {
				break;
			}
			asa++;
			
			
			a:for (int i = 1; i < graphtopoints.size()-1; i++) {
				Point points = null;
				Point pointm = null;
				Point pointe = null;
				if (i==(graphtopoints.size()-1)) {
					points = graphtopoints.get(i-1);
					pointm = graphtopoints.get(i);
					pointe = graphtopoints.get(0);
				}if (i==graphtopoints.size()) {
					points = graphtopoints.get(graphtopoints.size()-1);
					pointm = graphtopoints.get(0);
					pointe = graphtopoints.get(1);
				}else {
					points = graphtopoints.get(i-1);
					pointm = graphtopoints.get(i);
//					System.out.println("iiiiiiiiiiiiiiiiiiiiii"+i+"    "+(graphtopoints.size()-1));
					pointe = graphtopoints.get(i+1);
				}
				
				
				

				boolean leftTest = ToLeftTest.toLeftTest(pointm, points, pointe);
				
				if (leftTest) {//如果在左侧，这个点就不是耳朵点了，不能割
					continue;
				}
				for (int j = 0; j < graphtopoints2.size(); j++) {//这条割线不能包含其他点
					Point point = graphtopoints2.get(j);
					if (point.equals(points)||point.equals(pointm)||point.equals(pointe)) {
						continue;
					}
					boolean isok = ToLeftTest.inTriangleTest(point, points,pointm, pointe);
					if (isok) {//这个三角形内部不能有顶点
//						System.out.println("这个是内循环点："+i);
						continue a;
					}
				}
				
				
				
				
				
				//如果是耳朵，那么这个点就要被去除
				
				graphtopoints.remove(pointm);
				Line line = new Line();
				line.spoint = points;
				line.epoint = pointe;

				lineangle.add(line);
				
				break;
				
			}
			
		}
		
		for (int j = 0; j < graphtopoints.size(); j++) {
			System.out.println(graphtopoints.get(j));

		}
		
		
		
		System.out.println(lineangle.size());
		for (int i = 0; i < lineangle.size(); i++) {
		
			System.out.println(lineangle.get(i));
			
		}
		
		
		return lineangle;
		
	}
	
	
	
	
	
	public static Graph inittu() {
		
		Line line1 = new Line();
		Line line2 = new Line();
		Line line3 = new Line();
		Line line4 = new Line();
		Line line5 = new Line();
		Line line6 = new Line();
		Line line7 = new Line();
		Line line8 = new Line();

		
		
		Point point1 = new Point();
		point1.x = 1;
		point1.y = 0;

		Point point2 = new Point();
		point2.x = 2;
		point2.y = 0;
		
		Point point3 = new Point();
		point3.x = 3;
		point3.y = 1;
		
		Point point4 = new Point();
		point4.x = 3;
		point4.y = 2;
		
		Point point5 = new Point();
		point5.x = 2;
		point5.y = 3;
		
		Point point6 = new Point();
		point6.x = 1;
		point6.y = 3;
		
		Point point7 = new Point();
		point7.x = 2;
		point7.y = 2;
		Point point8 = new Point();
		point8.x = 2;
		point8.y = 1;
		
		line1.spoint = point1;
		line1.epoint = point2;
		line2.spoint = point2;
		line2.epoint = point3;
		line3.spoint = point3;
		line3.epoint = point4;
		line4.spoint = point4;
		line4.epoint = point5;
		line5.spoint = point5;
		line5.epoint = point6;
		line6.spoint = point6;
		line6.epoint = point7;
		line7.spoint = point7;
		line7.epoint = point8;
		line8.spoint = point8;
		line8.epoint = point1;
		
		
		List<Line> lines = new ArrayList<Line>();
		lines.add(line1);
		lines.add(line2);
		lines.add(line3);
		lines.add(line4);
		lines.add(line5);
		lines.add(line6);
		lines.add(line7);
		lines.add(line8);

		
		
		Graph graph = new Graph();
		graph.lines = lines;
		
		return graph;
		
	}
	
	
	
	
	
	
	
	
	
	
	
	

}
